package algorithm.swordoff;


/**
 * 旋转数组的最小数字
 *
 * 问题: 有重复数字的旋转数组的查找
 * 从简单到复杂去考虑:
 *     1.如果排好序不旋转,那么就是第一个元素
 *     2.如果旋转但是不带重复数字(类似leetcode第33题,只是判断条件不是找目标值而是找2个排序数组的分界点,nums[mid]比左边小就找左边,比右边大就找右边)
 *     3.(本题)旋转又带重复,思路:二分和暴力搜索交替使用
 *          - 如果nums[mid]严格的小于或者大于右边,那么是可以知道分界点在哪边的
 *          - 如果nums[mid]等于小于或者大于右边,这种情况将搜索范围从n缩减到n-1(暴力法),右指针-1
 *            思考:为什么右指针-1这个操作不会对结果产生影响？当且仅当右指针指向的元素是唯一的最小元素会对结果产生影响,
 *                而进入这个步骤的前提是nums[mid]等于小于或者大于右边,矛盾
 */

public class SQ11 {

    public int minArray(int[] numbers) {
        int left = 0, right = numbers.length-1;
        int mid;

        while (left < right) {
            mid = (right - left)/2 + left;

            // 如果中间的数比右边的大,说明分界点肯定在右边,注意left=mid+1,因为mid不可能是最小元素,多向右移动一个
            if (numbers[mid] > numbers[right]) left = mid+1;
            // 如果中间的数比左边的小,说明分界点肯定在左边,但是这里mid可能是最小元素,将其囊括进去
            else if (numbers[mid] < numbers[left]) right = mid;
            // 如果相等,使用暴力法,把上面两个if里面的条件分别看看成事件A和事件B,下面这个else隐含条件就是if (!A && !B)
            else right--;
        }

        return numbers[left];
    }

    public static void main(String[] args) {
        int[] a = {3,4,5,1,2};
        SQ11 sq11 = new SQ11();
        System.out.println(sq11.minArray(a));

    }
}
